package com.hjr.leetcode.question100;


import java.util.HashSet;

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 */
public class q3 {

    public static void main(String[] args) {
        String s = "dvdf";
        System.out.println(lengthOfLongestSubstring1(s));
    }

    //61ms 44mb
    public static int lengthOfLongestSubstring(String s) {
        //利用set来存储且判断是否重复
        HashSet<Character> set = new HashSet<>();
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            if (!set.add(s.charAt(i))) {
                //拿现在和前面的不重复的子串较大的长度
                length = Math.max(length, set.size());
                //将下标移动开始循环的后一个元素，保证不漏掉长字符
                i = i - set.size();
                //重新开始计算长度
                set.clear();
            }
        }
        //上面都是重复后触发计算，如果最长字符串在最后，需要额外计算一次
        length = Math.max(length, set.size());
        //如果没有长度，直接取字符串长度
        if (length == 0){
            length = s.length();
        }
        return length;
    }

    //滑动窗口解决 7ms 43mb
    public static int lengthOfLongestSubstring1(String s) {
        //利用set来存储且判断是否重复
        HashSet<Character> set = new HashSet<>();
        int ans = 0;
        int length = s.length();
        int rk = -1;
        for (int i = 0; i < length; i++) {
            if (i != 0){
                set.remove(s.charAt(i - 1));
            }
            while (rk + 1 < length && !set.contains(s.charAt(rk + 1))){
                set.add(s.charAt(rk + 1));
                rk++;
            }
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

}
